1. Field of the Invention
The present invention relates to a processing apparatus for solving an optimizing problem using simulated annealing (hereinafter, referred to as SA) and a method thereof.
2. Description of the Related Art
In recent years, in order to solve problems in various fields, it has become necessary to solve relatively large optimizing problems. The SA is a general-purpose solving method for solving such optimizing problems. The SA has been successfully used for optimizing problems such as cell placing problems in VLSI (very large scale integration) design and scheduling in production process.
In the annealing method, a substance is heated to a high temperature and then gradually cooled so that the energy thereof physically becomes the minimum state (ground state). In a system to be evaluated, evaluating energy is defined. An annealing process of the system is simulated corresponding to metropolis procedure so as to optimize the state of the system. This technique is referred to as SA.
Next, the algorithm of conventional SA will be described. First, assume a system that is composed of many objects that have various states. The sum of states of all the objects is the state of the system. As a real function of the state of the system, energy is defined. When SA is applied for a problem of a combination, energy is defined corresponding to an evaluation value of the combination. As the energy is low, the evaluation is high.
Next, objects are selected in a proper order. For each object, the metropolis procedure is applied. States of alternatives with probabilities are designated to each object. A system energy Ef in the state of an alternative designated to each object and a system energy En in the present state are calculated. On the other hand, random numbers in the range from 0 to 1 are uniformly generated. The generated random numbers are denoted by r. A temperature parameter is denoted by T. When exp[xe2x88x92(Efxe2x88x92En)/T]xe2x89xa7r, each object is designated to the state of the alternative. On the other hand, when exp[xe2x88x92(Ef=En)/T] less than r, each object is kept in the present state.
When this operation is continued with T (constant), the system converges to a Gibbs distribution due to the temperature T and the system energy. When T is gradually decreased and approaches O, the system converges to a state of which the minimum value or semi-minimum value of energy is given. The latter is referred to as SA due to an analogy of a physical phenomenon. In particular, a temperature change schedule is referred to as an annealing schedule. Logically, it has been proved that when the temperature T is very gradually decreased, the system converges to a state of which the minimum value of the energy is given. However, practically, so as to reduce the process time, the temperature is relatively quickly decreased.
The SA has the following advantages. As a first advantage, it is logically assured that the system converges to an optimum solution. In reality, the system converges to an optimum solution or a semi-optimum solution. As a second advantage, since the SA can be generally used, it can be easily applied for various problems. As a third advantage, functions that represent system energy or restricting condition have almost no restrictions and they may be discontinuous.
However, as described above, since the algorithm of the SA is basically a sequence of simple operations that determine whether or not to accept the state of the next alternative, it may take a very long time. In addition, the acceptance of the state of the alternative depends on the difference of energy in the present state and the state of the alternative. Thus, the state is not always accepted. When the state of the alternative is not accepted, since the system remains in the present state, the convergence of the system is further delayed.
In other words, when the SA is used, a good solution can be finally obtained. However, it takes a very long time to obtain a solution. Thus, it is necessary to perform the system at a high speed.
An object of the present invention is to modify the algorithm of the SA so as to provide a processing apparatus for solving an optimizing problem at high speed and a method thereof.
As an aspect of the present invention, when determining whether or not to transit the present state to the next state, an alternative of the next state is selected so that the probability for accepting the alternative of the next state becomes high. In other words, the probability for selecting the alternative of the next state is designated so that the alternative is accepted as the next state with a high probability. Thus, the simulated annealing process can be performed at high speed, thereby contributing to solving various optimizing problems.
These and other objects, features and advantages of the present invention will become more apparent in light of the following detailed description of best mode embodiments thereof, as illustrated in the accompanying drawings.